The present invention relates generally to the field of digital signal processing involving computer arithmetic, and more specifically relates to a system and method for comparing two binary numbers with a power-of-two threshold.
Binary comparators for comparing two or more binary numbers are well known in the art, as are methods for increasing the speed and efficiency of the comparison process. However, a more difficult problem is that of comparing two numbers with a threshold, namely, the result of the relation y less than x+k, where x and y are two numbers to be compared and k is a threshold. A typical solution to this problem is to compute the sign of xe2x88x92y+x+k. One conventional approach to performing this sign computation has been to use a layer of full-adders in order to generate sum and carry_out signals (s and c, respectively) such that s+c=xe2x88x92y+x+k, followed by a fast carry generation scheme, such as carry-lookahead or carry-select, to generate the output carry of the addition s+c. This output carry is the result of the comparison. An implementation of this conventional scheme is illustrated in FIGS. 1A through 1D.
With reference to the overall conventional system block diagram shown in FIG. 1D, two n-bit binary numbers, x and y (in this case, n=8), are first pre-added with a power-of-two threshold, in this case a threshold of 16, by a conventional adder stage 102 (designated as xe2x80x9cBOX Axe2x80x9d). The details of the adder stage 102 are illustrated in FIG. 1A, wherein corresponding bits of the two input numbers x and y are connected to inputs xe2x80x9cAxe2x80x9d and xe2x80x9cBxe2x80x9d of a full adder circuit 110 and the threshold bit is connected to the carry_in input of the full adder 110. The full adder circuit 110 generally includes at least one exclusive-OR gate, along with other logic gates, to generate sum and carry out outputs, s and c, respectively. The use of exclusive-OR gates adds significant cost and delay to the overall circuit and is thus not desirable. The sum and carry_out signals generated for each of the corresponding bits of the input numbers x and y are subsequently fed to n+1 kill-propagate (or generate-propagate) stages 104 (designated as xe2x80x9cBOX Bxe2x80x9d). Each kill-propagate stage 104 receives as inputs a sum signal associated with a particular bit, b, and a carry_out signal associated with a preceding bit, bxe2x88x921, of the input numbers. The details of the kill-propagate stage 104 are shown in FIG. 1B, wherein a generate output, g, is generated as a logical AND 112 of the two input signals and a kill or propagate signal, k, is generated as a logical OR 114 of the two input signals.
With continued reference to the conventional example of FIG. 1D, the generate and kill signals from the kill-propagate stages 104 are subsequently fed to a compare tree consisting of recursive kill-propagate stages 106 (designated as xe2x80x9cBOX Cxe2x80x9d), the details of which are shown in FIG. 1C. The number of generate and kill outputs are successively reduced at each level of recursive stages 106, until a single output corresponding to the desired result y greater than x+16 is obtained.
An interesting special case occurs when the threshold in the comparison is a power of two (i.e., 2k). This case appears in the add-carry-select structure of a maximum-likelihood detector when the inputs have been properly scaled. The add-carry-select circuit is critically flawed, however, in the sense that it cannot be easily pipelined. Moreover, the extra addition required to initially reduce the three input numbers into two numbers is costly in terms of circuit complexity and speed, among other factors, since this topology requires three-input exclusive-OR (XOR) gates. In fact, approximately one third of the total propagation delay of the circuit can be attributed to the XOR gates employed in the conventional architecture.
There is a need, therefore, in the field of computer arithmetic involving the comparison of two binary numbers with a power-of-two threshold, to provide an architecture and method which avoids the extra level of addition, thereby eliminating the use of exclusive-OR logic gates, and which may be easily pipelined.
The present invention provides methods and apparatus for comparing two numbers having a power-of-two threshold, y greater than x+2k, that does not require the two numbers and the threshold to be pre-added. In this manner, the present invention eliminates the need for exclusive-OR (XOR) logic gates which are costly and add significant propagation delay to the overall circuit.
In one illustrative aspect of the invention, an architecture is provided which addresses the issue of comparing two binary numbers with a power-of-two threshold by employing a comparator circuit which provides an output signal corresponding to the relation y greater than x+2k. By defining new relations, namely, much_greater_than (ggi) and equal_to (nqi), based at least in part on generate (gt) and propagate (eq) signals created for each bit of the binary numbers to be compared, and by applying recursion in order to reduce the set of input signals at subsequent nodes or levels of recursion by a predetermined number, the XOR gates may be eliminated, thereby significantly reducing the overall cost of the circuit and essentially eliminating other disadvantages present in conventional methods and apparatus.
These and other objects, features and advantages of the present invention will become apparent from the following detailed description of illustrative embodiments thereof, which is to be read in connection with the accompanying drawings.